/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package mamayukero.logic.pathfinding;

import java.awt.Point;
import java.util.ArrayList;
import mamayukero.debug.LogContainer;
import mamayukero.problem.environment.map.Map;
import mamayukero.problem.environment.map.Path;

public class Greedy extends PathFindingBase {
    
    public Greedy(Map map) {
        super(map);
        log = new LogContainer("Greedy");
    }

    @Override
    public Path solve(Point start, Point end) {
        this.start = start;
        this.end = end;
        path = new Path(start,end);
        log.append("Mencari jalan dari [" + start.x + "," + start.y + "]" + " ke " + "[" + end.x + "," + end.y + "]");
        path.setPoint(solveGreedy());
        StringBuilder pathString = new StringBuilder("Menemukan jalan : ");
        for (Point p: path.point) {
            pathString.append("[").append(p.x).append(",").append(p.y).append("]");
        }
        log.append(pathString.toString());
        return path;
    }
    
    public ArrayList<Point> solveGreedy() 
	{
		//printAllStraightLines();
		
		//solution path
		ArrayList<Point> tSol = new ArrayList<Point>();
		
		//list of visited points
		ArrayList<Point> tVisitedPs = new ArrayList<Point>();
		
		//moveable points for each expansion, not including already visited points
		ArrayList<Point> tMoveablePs;
		
		Point tCurP = start;
		boolean isSol = false;
		
		while (!isSol)
		{
			tSol.add(tCurP.getLocation());
			
			if (!tCurP.equals(end)) {
				//add current point to visited points
				tVisitedPs.add(tCurP.getLocation());
				
				//expand current position
				tMoveablePs = notVisitedPoints(tCurP, tVisitedPs);
				
				//find cheapest point for next point
				tCurP = findShortest(tMoveablePs);
			} else {
				//goal found
				isSol = true;
			}
		}
		return tSol;
    }
	
	private ArrayList<Point> notVisitedPoints(Point pCurP, ArrayList<Point> pVisitedNodes)
	{
		ArrayList<Point> tMoveablePs = whereToGo(pCurP.x, pCurP.y, map);		
		boolean found=false;
		int i=0;
		while (!found && i<tMoveablePs.size())
		{
			if (pVisitedNodes.contains(tMoveablePs.get(i))) {
				found = true;
			}
			i++;
		}
		if (found) {
			i--;
			tMoveablePs.remove(i);
		}
		return tMoveablePs;
	}
	
	private void printAllStraightLines()
	{
		int iRow,iCol;
		for (iRow=0;iRow<map.row;iRow++)
		{
			for (iCol=0;iCol<map.col;iCol++)
			{
				System.out.println("["+iRow+","+iCol+"]: "+ new Point(iRow, iCol).distance(end));
			}
		}
	}
	
	/**
	 * Search a point with the shortest distance to the end point
	 * @param pPoints
	 * @return shortest distance point to end point
	 */
	private Point findShortest(ArrayList<Point> pPoints)
	{
		Point tPoint = pPoints.get(0);
		int i;
		for (i=1;i<pPoints.size();i++)
		{
			if (pPoints.get(i).distance(end) < tPoint.distance(end)) {
				tPoint = pPoints.get(i);
			}
		}
		return tPoint.getLocation();
	}
}